package com.hy;

import java.util.Arrays;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:并查集框架代码
 * User:Mr.Du
 * Date:2023/9/15
 * Time:11:35
 */
public class QuickUnionUF {

    public int[] roots;

    public QuickUnionUF(int n){
        roots = new int[n];
        // 初始化，自己就是老大
        for(int i = 0;i < n;i++){
            roots[i] = i;
        }
    }

    /**
     * 递归实现-查找老大
     * @param i
     * @return
     */
    public int findRoot1(int i){
        if(i == roots[i]){
            return i;
        }
        roots[i] = findRoot(roots[i]);
        return roots[i];
    }

    /**
     * 迭代实现-查找老大
     * @param i
     * @return
     */
    public int findRoot(int i){
        int root = i;
        // 找到i的老大--> i的老大是j，j的老大是m，m的老大是n，那么i的最终老大就是n
        // i->j->m->n
        while(root != roots[root]){
            root = roots[root];
        }
        // 路径压缩，如：i->j->m->n
        // 直接将i到n之间所有节点都连到n上面
        // 即：i, j, m --> n
        while(i != roots[i]){
            // 记录i的顶头上司tmp
            int tmp = roots[i];
            // 把i的顶头上司改为隐藏身后的大boss
            roots[i] = root;
            // 继续更改tmp的顶头上司
            i = tmp;
        }
        return root;
    }


    public boolean connected(int p, int q){
        return findRoot(p) == findRoot(q);
    }

    public void union(int p, int q){
        int pRoot = findRoot(p);
        int qRoot = findRoot(q);
        roots[pRoot] = qRoot;
    }

    public static void main(String[] args) {
        QuickUnionUF quickUnionUF = new QuickUnionUF(1005);
        // [[1,2],[2,3],[3,4],[1,4],[1,5]]
        int[][] edges = {{1,2},{2,3},{3,4},{4,1},{1,5}};
        int[] res = quickUnionUF.findRedundantConnection(edges);
        System.out.println(Arrays.toString(res));
    }

    public int[] findRedundantConnection(int[][] edges) {
        for(int i = 0;i < edges.length;i++){
            if(connected(edges[i][0], edges[i][1])){
                return edges[i];
            }else{
                union(edges[i][0], edges[i][1]);
            }
        }
        return null;
    }
}
